#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

//void find(int* arr,int key,int sz)
//{
//	int count = 0;
//	for (int j = 0; j < sz; j++)
//	{
//		if (arr[j] == key)
//			count++;
//	}
//	if (count == 1)
//	{
//		printf("%d\n", key);
//	}
//}
//int main()
//{
//	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
//	int len = sizeof(arr) / sizeof(arr[0]);
//	for (int i = 0; i < len; i++)
//	{
//		int key = arr[i];
//		find(arr,key,len);
//	}
//	return 0;
//}

//找单身狗2
void find(int arr[],int sz,int* pd1,int* pd2)
{
	// 0 ^ 0 = 0;
	// 0 ^ 任何数 = 任何数
	//所有数字异或在一起，找到两个单身狗异或的结果
	int ret = 0;
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}
	//ret二进制中为1的那一位，就是两个单身狗不同的位数，
	//找到这个位置，以这个位置为分界线，来区分单身狗
	int pos = 0;
	for (i = 0; i < sz; i++)
	{
		if (((ret >> i) & 1) == 1)
		{
			pos = i;  //找到这个位置
			break;
		}
	}
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			*pd1 ^= arr[i];
		}
	}
	/*for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 0)
		{
			*pd2 ^= arr[i];
		}
	}*/
	//此时已经找到一个单身狗了，同时也知道两个单身狗异或的值，所以另一个单身狗可以直接求得
	*pd2 = ret ^ *pd1;
}
int main()
{
	int arr[] = { 1,2,3,4,7,1,2,3,4,15 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int dog1 = 0;
	int dog2 = 0;
	find(arr, sz,&dog1,&dog2);
	printf("%d %d ", dog1, dog2);
	return 0;
}